The growth of the Internet and the increasing sophistication and availability of cryptographic tools have led to the widespread implementation of numerous electronic commerce applicaticns, including on-line shopping, banking and other activities, all of which may be broadly described as "trading." The improved efficiency of such electronic commerce applications is attributable to a number of factors, including minimized human involvement, improved distribution of goods and information, and more rapid processing of transactions. Ideally, prospective traders should be able to locate one another in a highly automated fashion and then execute trades with strong security guarantees.
Since the introduction of payment schemes to the field of cryptography by D. Chaum, A. Fiat and M. Naor, "Untraceable Electronic Cash," Advances in Cryptology--Proceedings of Crypto '88, pp. 319-327, subsequent developments have tended either to introduce new features into existing payment paradigms or to address stronger attack models. Among the new features recently introduced are off-line payments, as described in, e.g., S. Brands, "Untraceable Off-line Cash in Wallets with Observers," Advances in Cryptology--Proceedings of Crypto '93, pp. 302-318; divisibility, as described in, e.g., T. Okamoto, "An Efficient Divisible Electronic Cash Scheme," Advances in Cryptology--Proceedings of Crypto '95, pp. 438-451; and micro-payments, as described in, e.g., R. Rivest and A. Shamir, "PayWord and MicroMint: Two Simple Micropayment Schemes," Cryptobytes, Vol. 2, Num. 1, 1996, pp. 7-11.
Examples of stronger attack models or improved protection against attacks include tamper-resistance, as described in, e.g., D. Chaum and T. Pedersen, "Wallet databases with observers," Advances in Cryptology--Proceedings of Crypto '92, pp. 89-105; provable security against forgery, as described in, e.g., A. Juels, M. Luby and R. Ostrovsky, "Security of Blind Digital Signatures," Advances in Cryptology--Proceedings of Crypto '97, pp. 150-164; fairness, as described in, e.g., M. Jakobsson, "Ripping Coins for a Fair Exchange," Advances in Cryptology--Proceedings of Eurocrypt '95, pp. 220-230; probabilistic on-line verification, as described in, e.g., S. Jarecki and A. Odlyzko, "An Efficient Micropayment System Based on Probabilistic Polling," Advances in Cryptology--Proceedings of Financial Cryptography '97, pp. 173-191; and revocable anonymity, as described in, e.g., M. Jakobsson and M. Yung, "Applying Anti-Trust Policies to Increase Trust in a Versatile E-Money System," Advances in Cryptology--Proceedings of Financial Cryptography '97, pp. 217-238.
These and other conventional techniques, however, often assume that the trading process starts at a point where there are two parties who are aware of each other's existence and whereabouts and wish to perform a transfer of funds and merchandise. Although such an assumption may be appropriate for a conventional peer-to-peer commercial setting, it is not necessarily true for the type of settings which are common in electronic commerce, i.e., settings in which there are large numbers of uncoordinated and distributed participants potentially willing to engage in trades, but unaware of each other's trade goals. It is possible in such settings to let prospective trading partners seek each other out and then initiate peer-to-peer transactions. This, however, increases the risk of communication bottlenecks, since, e.g., communicating with the originator of an offer may require costly traversals of a network. In addition, if the originator of an offer receives many bids but has limited computational power, this type of commerce could overtax his or her computational resources.
A possible alternative method of establishing first contact between traders involves the use of "mobile agents," as described in, e.g., D. Rus, R. Gray and D. Kotz, "Transportable Information Agents," 1st Intl. Conf. Autonomous Agents, 1997. Mobile agents may be viewed as program segments which are sent across a network and execute on host machines. Their aim is to perform some task on behalf of a corresponding user with a certain degree of autonomy. Proposed uses include bartering, negotiating, entertainment, monitoring, data selection and filtration, searching, and distributed processing. However, the conventional payment schemes noted above are generally not well adapted for use with mobile agents. For example, if a mobile agent carries conventional digital cash, it may be vulnerable to "pick-pocketing," as described in, e.g., B. Venners, "Solve Real Problems with Aglets, a Type of Mobile Agent," Javaworld, May 1997. On the other hand, not allowing mobile agents to carry fluids to perform commerce requires a reduction to the peer-to-peer setting with its attendant bottlenecks.
Another technique which has been proposed for use in electronic commerce applications is known as "challenge semantics" and is described in M. Jakobsson and M. Yung, "Revokable and Versatile Electronic Money," 3rd ACM Conference on Computer and Communications Security, 1996, pp. 76-87. This technique uses the challenge of a payment to indicate the conditions of the trade. However, it generally only allows a designation of the payment to be specified, and fails to provide an adequate solution to the above-noted problem of agent-based trade.